package mao.leetcode.others.leetcode112;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {


    //如何提前结束递归流程，如果找到，怎么没提前结束，而不是继续找下去。
  ///  boolean flag = false;
//    public boolean hasPathSum(TreeNode root, int sum) {
//        if (root == null) return false;
//        if (root.right == null && root.left == null) {
//            if (root.val == sum) {
//                return true;
//            }else return false;
//        }else {
//            sum-=root.val;
//            return hasPathSum(root.left,sum) || hasPathSum(root.right,sum); //短路或
//        }
//    }
       //递归写法
        public boolean hasPathSum_1(TreeNode root, int sum) {
        if (root == null) return false;
        if (root.right == null && root.left == null)
              return root.val == sum;
        sum-=root.val;
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum); //短路或
         }

    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right=node3;
        node2.left=node4;
        node2.right=node5;
        hasPathSum(node1,8);

    }
         //栈实现深度优先,有点麻烦就先不实现了
      public static boolean hasPathSum(TreeNode root, int sum) {
          List<Integer> list = new ArrayList<>();
          Stack<TreeNode> stack = new Stack<>(); //需要处理的
          TreeNode cur = root;  //正在处理的
          while (cur != null || !stack.isEmpty()){
              while (cur != null){  //递归左侧，由于一直查找到 cur == null 所以右侧节点也可以被处理。
                  stack.push(cur);
                  sum-=cur.val;
                  cur = cur.left;
              }
              cur = stack.pop(); //每个被处理的节点都是先入栈，然后出栈。
             // if (cur == null)  continue;
              //*******
              sum+=cur.val;
              if (cur.left == null && cur.right == null) {
                  if (sum == cur.val) return true;
              }
              //list.add(cur.val); //递归中间
              cur= cur.right;    //处理右侧
          }
          return false;
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
